#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include "Iterator.h"

// B+树节点定义
template <typename T, int Order>
struct b_plus_tree_node {
    bool is_leaf;                   // 是否为叶子节点
    int key_count;                  // 当前关键字数量
    T keys[Order - 1];              // 关键字数组
    b_plus_tree_node* children[Order];  // 子节点数组
    b_plus_tree_node* next;         // 叶子节点的下一个节点指针

    // 构造函数
    b_plus_tree_node() : is_leaf(true), key_count(0), next(nullptr) {
        for (int i = 0; i < Order; ++i) {
            children[i] = nullptr;
        }
    }

    // 查找关键字位置
    int find_key(const T& key) const {
        int idx = 0;
        while (idx < key_count && keys[idx] < key) {
            ++idx;
        }
        return idx;
    }
};

// B+树迭代器
template <typename T, int Order>
class b_plus_tree_iterator 
    : public my_stl::iterator<my_stl::bidirectional_iterator_tag, T> {
public:
    using value_type = T;
    using reference = T&;
    using pointer = T*;
    using difference_type = ptrdiff_t;
    using iterator_category = my_stl::bidirectional_iterator_tag;
    using self = b_plus_tree_iterator<T, Order>;
    using node = b_plus_tree_node<T, Order>;

private:
    node* current_node;  // 当前叶子节点
    int current_index;   // 当前关键字索引

public:
    b_plus_tree_iterator() : current_node(nullptr), current_index(-1) {}
    b_plus_tree_iterator(node* leaf, int idx = 0) : current_node(leaf), current_index(idx) {

        if (current_node && (current_index < 0 || current_index >= current_node->key_count)) {
            current_node = nullptr;
            current_index = -1;
        }
    }

    // 解引用操作符
    reference operator*() const {
        if (!current_node || current_index < 0 || current_index >= current_node->key_count) {
            throw std::out_of_range("B+树迭代器：解引用无效迭代器");
        }
        return current_node->keys[current_index];
    }

    // 成员访问操作符
    pointer operator->() const {
        return &(operator*());
    }

    // 前置++
    self& operator++() {
        if (!current_node) return *this;

        if (current_index + 1 < current_node->key_count) {
            current_index++;
            return *this;
        }

        current_node = current_node->next;
        current_index = 0;

        if (!current_node || current_node->key_count == 0) {
            current_node = nullptr;
            current_index = -1;
        }

        return *this;
    }

    // 后置++
    self operator++(int) {
        self temp = *this;
        ++(*this);
        return temp;
    }

    // 前置--
    self& operator--() {
        if (!current_node) return *this;

        if (current_index > 0) {
            current_index--;
            return *this;
        }

        throw std::runtime_error("B+树迭代器：--操作未完全实现");
        return *this;
    }

    // 后置--
    self operator--(int) {
        self temp = *this;
        --(*this);
        return temp;
    }

    // 相等比较
    bool operator==(const self& other) const {
        return current_node == other.current_node && current_index == other.current_index;
    }

    // 不等比较
    bool operator!=(const self& other) const {
        return !(*this == other);
    }
};

// B+树类定义
template <typename T, int Order>
class b_plus_tree {
    static_assert(Order >= 3, "B+树的阶数必须至少为3");

private:
    using node = b_plus_tree_node<T, Order>;
    node* root;          // 根节点
    node* leaf_head;     // 叶子节点链表头
    int node_count;      // 节点数量
    int element_count;   // 元素总数
    const int max_keys;  // 每个节点最多关键字数
    const int min_keys;  // 每个节点最少关键字数

    // 销毁节点
    void destroy_node(node* n) {
        if (!n) return;
        if (!n->is_leaf) {
            for (int i = 0; i <= n->key_count; ++i) {
                destroy_node(n->children[i]);
            }
        }
        delete n;
        node_count--;
    }

    // 分裂叶子节点
    void split_leaf(node* parent, int child_idx) {
        node* leaf = parent->children[child_idx];
        node* new_leaf = new node();
        new_leaf->is_leaf = true;
        new_leaf->next = leaf->next;
        leaf->next = new_leaf;

        // 复制关键字
        int mid = max_keys / 2;
        for (int i = 0; i < max_keys - mid; ++i) {
            new_leaf->keys[i] = leaf->keys[mid + i];
        }
        new_leaf->key_count = max_keys - mid;
        leaf->key_count = mid;

        // 更新父节点
        for (int i = parent->key_count; i > child_idx; --i) {
            parent->keys[i] = parent->keys[i - 1];
            parent->children[i + 1] = parent->children[i];
        }
        parent->keys[child_idx] = new_leaf->keys[0];
        parent->children[child_idx + 1] = new_leaf;
        parent->key_count++;
        node_count++;
    }

    // 分裂内部节点
    void split_internal(node* parent, int child_idx) {
        node* internal = parent->children[child_idx];
        node* new_internal = new node();
        new_internal->is_leaf = false;

        // 复制关键字和子节点
        int mid = (max_keys - 1) / 2;
        T mid_key = internal->keys[mid];

        // 复制后半部分关键字
        for (int i = 0; i < max_keys - mid - 1; ++i) {
            new_internal->keys[i] = internal->keys[mid + 1 + i];
        }
        // 复制子节点指针
        for (int i = 0; i < max_keys - mid; ++i) {
            new_internal->children[i] = internal->children[mid + 1 + i];
        }

        new_internal->key_count = max_keys - mid - 1;
        internal->key_count = mid;

        // 更新父节点
        for (int i = parent->key_count; i > child_idx; --i) {
            parent->keys[i] = parent->keys[i - 1];
            parent->children[i + 1] = parent->children[i];
        }
        parent->keys[child_idx] = mid_key;  // 中间关键字上移
        parent->children[child_idx + 1] = new_internal;
        parent->key_count++;
        node_count++;
    }

    // 插入非满节点
    void insert_non_full(node* n, const T& key) {
        if (n->is_leaf) {
            int i = n->key_count - 1;
            while (i >= 0 && key < n->keys[i]) {
                n->keys[i + 1] = n->keys[i];
                i--;
            }
            n->keys[i + 1] = key;
            n->key_count++;
            element_count++;
        } else {
            int i = n->key_count - 1;
            while (i >= 0 && key < n->keys[i]) {
                i--;
            }
            i++;

            // 检查子节点是否满
            if (n->children[i]->key_count == max_keys) {
                // 根据子节点类型选择分裂方式
                if (n->children[i]->is_leaf) {
                    split_leaf(n, i);
                } else {
                    split_internal(n, i);
                }

                if (key > n->keys[i]) {
                    i++;
                }
            }
            insert_non_full(n->children[i], key);
        }
    }

    // 查找关键字所在的叶子节点
    node* find_leaf(const T& key) const {
        if (!root) return nullptr;

        node* current = root;
        while (!current->is_leaf) {
            int i = 0;
            while (i < current->key_count && key > current->keys[i]) {
                i++;
            }
            current = current->children[i];
        }
        return current;
    }

    // 检查B+树有效性
    bool is_valid_helper(node* n, int& height, T* min_val, T* max_val, bool is_leaf) const {
        if (!n) return true;

        // 检查节点类型一致性
        if (n->is_leaf != is_leaf && height > 1) return false;

        // 检查关键字数量是否合法
        if (n == root) {
            if (n->key_count < 1 && node_count > 1) return false;
        } else {
            if (n->key_count < min_keys || n->key_count > max_keys) return false;
        }

        // 检查关键字是否有序
        for (int i = 0; i < n->key_count - 1; ++i) {
            if (n->keys[i] >= n->keys[i + 1]) return false;
        }

        // 检查最小值和最大值约束
        if (min_val && n->keys[0] < *min_val) return false;
        if (max_val && n->keys[n->key_count - 1] > *max_val) return false;

        // 叶子节点高度为1
        if (n->is_leaf) {
            height = 1;
            return true;
        }

        if (n->children[0] == nullptr) return false;
        if (n->key_count + 1 != get_child_count(n)) return false;

        // 递归检查子节点
        int child_height = 0;
        T child_min, child_max;

        // 检查第一个子节点
        child_max = n->keys[0];
        if (!is_valid_helper(n->children[0], child_height, min_val, &child_max, false)) {
            return false;
        }
        height = child_height + 1;

        // 检查中间子节点
        for (int i = 0; i < n->key_count - 1; ++i) {
            int current_height;
            child_min = n->keys[i];
            child_max = n->keys[i + 1];
            
            if (!is_valid_helper(n->children[i + 1], current_height, &child_min, &child_max, false)) {
                return false;
            }
            if (current_height != child_height) return false;
        }

        // 检查最后一个子节点
        child_min = n->keys[n->key_count - 1];
        if (!is_valid_helper(n->children[n->key_count], child_height, &child_min, max_val, false)) {
            return false;
        }

        return true;
    }

    // 获取子节点数量
    int get_child_count(node* n) const {
        int count = 0;
        while (count < Order && n->children[count] != nullptr) {
            count++;
        }
        return count;
    }

    // 打印B+树
    void print_helper(node* n, int level) const {
        if (!n) return;

        std::cout << "Level " << level << ": ";
        for (int i = 0; i < n->key_count; ++i) {
            std::cout << n->keys[i] << " ";
        }
        std::cout << "(叶节点: " << (n->is_leaf ? "是" : "否") << ")";
        if (n->is_leaf) {
            std::cout << " (下一个: " << (n->next ? "存在" : "空") << ")";
        }
        std::cout << std::endl;

        if (!n->is_leaf) {
            for (int i = 0; i <= n->key_count; ++i) {
                print_helper(n->children[i], level + 1);
            }
        }
    }

public:
    // 迭代器类型定义
    using iterator = b_plus_tree_iterator<T, Order>;
    using const_iterator = b_plus_tree_iterator<const T, Order>;

    // 构造函数
    b_plus_tree() : root(nullptr), leaf_head(nullptr), 
                   node_count(0), element_count(0),
                   max_keys(Order - 1), min_keys((Order - 1) / 2) {}

    // 析构函数
    ~b_plus_tree() {
        clear();
    }

    // 插入关键字
    void insert(const T& key) {
        if (search(key)) return;

        if (!root) {
            root = new node();
            root->is_leaf = true;
            root->keys[0] = key;
            root->key_count = 1;
            leaf_head = root;
            node_count = 1;
            element_count = 1;
            return;
        }

        // 如果根节点已满，分裂根节点
        if (root->key_count == max_keys) {
            node* new_root = new node();
            new_root->is_leaf = false;
            new_root->children[0] = root;
            node_count++;

            // 根据原根节点类型选择分裂方式
            if (root->is_leaf) {
                split_leaf(new_root, 0);
            } else {
                split_internal(new_root, 0);
            }
            root = new_root;
        }

        // 插入关键字
        insert_non_full(root, key);

        // 更新叶子链表头
        if (!leaf_head || root->is_leaf) {
            node* temp = root;
            while (temp && !temp->is_leaf) {
                temp = temp->children[0];
            }
            leaf_head = temp;
        }
    }

    // 查找关键字
    bool search(const T& key) const {
        node* leaf = find_leaf(key);
        if (!leaf) return false;

        // 在叶子节点中查找
        int i = leaf->find_key(key);
        return (i < leaf->key_count && leaf->keys[i] == key);
    }

    // 清空B+树
    void clear() {
        if (root) {
            destroy_node(root);
            root = nullptr;
        }
        leaf_head = nullptr;
        node_count = 0;
        element_count = 0;
    }

    // 获取元素数量
    int size() const {
        return element_count;
    }

    // 检查B+树是否为空
    bool empty() const {
        return element_count == 0;
    }

    // 检查B+树有效性
    bool is_valid() const {
        if (!root) return true;
        
        int height;
        return is_valid_helper(root, height, nullptr, nullptr, root->is_leaf);
    }

    // 打印B+树结构
    void print() const {
        if (!root) {
            std::cout << "B+树为空" << std::endl;
            return;
        }
        std::cout << "B+树结构 (阶数: " << Order << "):" << std::endl;
        print_helper(root, 0);
    }

    // 迭代器相关函数
    iterator begin() {
        return iterator(leaf_head, 0);
    }

    iterator end() {
        return iterator();
    }

    const_iterator begin() const {
        return const_iterator(leaf_head, 0);
    }

    const_iterator end() const {
        return const_iterator();
    }

    // 范围查询
    std::vector<T> range_query(const T& low, const T& high) const {
        std::vector<T> result;
        node* leaf = find_leaf(low);
        if (!leaf) return result;

        // 找到起始位置
        int i = leaf->find_key(low);
        while (leaf && i < leaf->key_count) {
            if (leaf->keys[i] > high) break;
            result.push_back(leaf->keys[i]);
            i++;
            // 当前叶子节点遍历完，移到下一个
            if (i >= leaf->key_count) {
                leaf = leaf->next;
                i = 0;
            }
        }
        return result;
    }
};